斯坦福算法专项课程Course1 Final Exam

这里回顾下第一门课的期末考试。

课程地址：https://www.coursera.org/specializations/algorithms

选择题 1

回想一下我们在QuickSort和RSelect中使用的Partition子例程。假设以下数组刚刚围绕某个pivot元素分区：3,1,2,4,5,8,7,6,9

哪些元素可能是pivot元素？（提示：检查所有适用的，可能有多种可能！）

pivot左边的元素要小于pivot，右边的元素要大于pivot，所以4,5,9均满足条件

选择题 2

这是一个十个整数的数组：5 3 8 9 1 7 0 2 6 4

假设我们在这个数组上运行MergeSort。在最外面的两个递归调用完成之后（即，在最后一个Merge步骤之前），部分排序数组的第7个位置的数字是多少？（当我们说“第7”位置时，我们是计算从1开始的位置；例如，输入数组在其第7位有一个“0”。）

最后一轮递归之前，数组的次序应该为1,3,5,8,9,0,2,4,6,7，所以第7个位置的元素为2

选择题 3

MergeSort的渐近最坏情况运行时间是什么，作为输入数组长度的函数$n$?

$\theta(n^2)$
$\theta(\log n)$
$\theta(n)$
$\theta(n\log n)$

显然答案为$\theta(n\log n)$

选择题 4

在长度为$n$的数组上数组使用Randomized QuickSort的期望运行时间以及最坏运行时间是多少？

$\Theta(n)$(期望)和$\Theta(n\log n )$(最坏情形)
$\Theta(n^2)$(期望)和$\Theta(n^2 )$(最坏情形)
$\Theta(n\log n)$(期望)和$\Theta(n\log n )$(最坏情形)
$\Theta(n\log n)$(期望)和$\Theta(n^2)$(最坏情形)

由第三周的内容可知，答案为第四项

选择题 5

两个非递减的正函数$f,g$满足$f= O(g(n))$，是否满足$2^{f(n)} = O(2^{g(n)})$

正确，如果$f(n) \le g(n)$对于所有足够大的$n$
有时正确
从不正确
总是正确

第一周选择题5，答案为第一项和第二项

选择题 6

令 $0<α<0.5 $是一个常数（与输入数组长度$n$无关）。回想一下QuickSort算法采用的Partition子程序，如讲座中所述。通过随机选择的pivot，Partition分割的两个子列中较小者的长度 $≥α$ 倍于原始数组的长度的概率？

$ 1 - 2\alpha$
$ \alpha$
$1-\alpha$
$2-2\alpha$

第三周选择题1，答案为第一项

选择题 7

假设随机算法成功（例如，正确地计算图的最小切割）的概率为$p$($ 0<p<1$)。令$\epsilon$是一个小的正数(小于1)。

需要运行算法多少次才能确保有大于等于 $1-\epsilon$的概率使得至少有一次试验成功？

$\frac{\log (p)}{\log \epsilon}$
$\frac{\log \epsilon }{\log (p)}$
$\frac{\log (1-p)}{\log \epsilon}$
$\frac{\log \epsilon }{\log (1-p)}$

运行算法$N$次，至少有一次算法成功的概率为$1-(1-p)^N$，令$1-(1-p)^N\ge 1- \epsilon$可得：

$\begin{aligned} 1-(1-p)^N&\ge 1- \epsilon \\ \epsilon &\ge (1-p)^N\\ \log \epsilon &\ge N \log (1-p)\\ N &\ge \frac{\log \epsilon }{\log (1-p)} \end{aligned}$

选择题 8

假设你得到了$k$个排好序的数组，每个都有个$n$元素，并且您希望将它们组合成有$kn$个元素的数组。考虑以下方法。把$k$个数组分成$k/2$对，并使用MergeSort讲座中讲授的Merge子例程来组合每一对。现在你有$k/2$个排好序的数组，每个都有$2n$个元素。重复此方法，合并为$kn$个元素的排好序的数组。这个程序的运行时间是多少？

$\theta(nk\log n) $
$\theta(n\log k) $
$\theta(nk^2) $
$\theta(nk\log k) $

第$i$轮要做$\frac k {2^{i}}$次merge，每次merge的数组长度为$2^{i-1} n$，所以每一轮需要的时间复杂度为

$\frac k {2^{i}} \times 2^{i-1}n \times 2 = kn$

一共需要运行$\log_2 k$轮，所以总时间为

$kn \log_2k$

时间复杂度为

$\theta(nk\log k)$

选择题 9

Strassen矩阵乘法算法的运行时间：假设算法的运行时间满足$ T(n)=7*T(n/2)+n^2$。$T(n)$为多少？

$\theta(n^2)$
$\theta(n^{\frac{\log 2}{\log 7}}) $
$\theta(n^2\log n)$
$\theta(n^{\log_2(7)})$

$a=7,b=2,d=2,a>b^d$，由主定理可得第四个选项正确。

选择题 10

回想一下Master Method及其三个参数$a,b,d$。以下哪项是对$b^d$最好的解释？

总工作量增长的速度（每个递归级别）。
子问题大小缩小的速率（每个递归级别）。
子问题数量增长的速率（每个递归级别）。
每个子工作问题的收缩率（每个递归级别）。

$T(n) \le aT(\frac n b) + O(n^d)$

画出递归树，可以知道$b^d$是每个子问题额外需要的时间的收缩率，所以第四项正确。